import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class LeetCode567 {
    public boolean checkInclusion(String s1, String s2) {
        s1 = sortString(s1);

        int s1Length = s1.length();
        int s2Length = s2.length();

        for (int i = 0; i <= s2Length - s1Length ; i++){
            String child = s2.substring(i, i + s1Length);
            child = sortString(child);
            if (child.equals(s1)){
                return true;
            }
        }

        return false;
    }


    public String sortString(String s){
        char[] arr = s.toCharArray();
        ArrayList<Character> characters = new ArrayList<>();

        for (int i = 0; i < arr.length; i++){
            characters.add(arr[i]);
        }

        characters.sort(new Comparator<Character>() {
            @Override
            public int compare(Character o1, Character o2) {
                if (o1.charValue() < o2.charValue()){
                    return -1;
                }

                if (o1.charValue() > o2.charValue()){
                    return 1;
                }
                return 0;
            }
        });
        StringBuilder sb = new StringBuilder();
        for (Character character: characters){
            sb.append(character.charValue());
        }

        return sb.toString();
    }



    public boolean checkInclusion1(String s1, String s2) {
        int[] s1CharNums = getCharNums(s1);

        int s1Length = s1.length();
        int s2Length = s2.length();

        for (int i = 0; i <= s2Length - s1Length ; i++){

            String child = s2.substring(i, i + s1Length);
            System.out.println(child);

            int[] childNums = getCharNums(child);
            if (equals(s1CharNums, childNums)){

                return true;
            }

            childNums = null;
        }

        return false;
    }

    public boolean checkInclusion2(String s1, String s2) {
        int[] s1CharNums = getCharNums(s1);

        int s1Length = s1.length();
        int s2Length = s2.length();

        if (s1Length > s2Length){
            return false;
        }

        int[] s2cns = new int[26];
        char[] s2Chars = s2.toCharArray();

        for (int i = 0; i < s1Length; i++){
            s2cns[s2Chars[i] - 'a'] += 1;
        }

        if (equals(s1CharNums, s2cns)){
            return true;
        }

        for (int k = s1Length; k < s2Length; k++){
            s2cns[s2Chars[k] - 'a']++;
            s2cns[s2Chars[k - s1Length] - 'a']--;

            if (equals(s1CharNums, s2cns)){
                return true;
            }
        }

        return false;
    }

    private boolean equals(int[] a1, int[] a2){
        for (int i = 0; i < 26; i++){
            if (a1[i] != a2[i]){
                return false;
            }
        }

        return true;
    }

    public int[] getCharNums(String s){
        int[] charNums = new int[26];

        char[] arr = s.toCharArray();

        for (int c: arr){
            charNums[c - 'a'] += 1;
        }

        return charNums;
    }
}
